Cosmological models that include suppression of the power spectrum of density fluctuations on small scales exhibit an exponential reduction of high-redshift, non-linear structures, including a reduction in the rate of gamma ray bursts (GRBs). Here we quantify the constraints that the detection of distant GRBs would place on structure formation models with reduced small-scale power. We compute the number of GRBs that could be detectable by the Swift satellite at high redshifts (z > 6), assuming that the GRBs trace the cosmic star formation history, which itself traces the formation of non-linear structures. We calibrate simple models of the intrinsic luminosity function of the bursts to the number and flux distribution of GRBs observed by the Burst And Transient Source Experiment (BATSE). We find that a discovery of high-z GRBs would imply strong constraints on models with reduced small-scale power. For example, a single GRB at z > 10, or 10 GRBs at z > 5, discovered by Swift during its scheduled two-year mission, would rule out an exponential suppression of the power spectrum on scales below R_c=0.09 Mpc (exemplified by warm dark matter models with a particle mass of m_x=2 keV). Models with a less sharp suppression of small-scale power, such as those with a red tilt or a running scalar index, n_s, are more difficult to constrain, because they are more degenerate with an increase in the power spectrum normalization, sigma_8, and with models in which star-formation is allowed in low-mass minihalos. We find that a tilt of \delta n_s ~ 0.1 is difficult to detect; however, an observed rate of 1 GRB/yr at z > 12 would yield an upper limit on the running of the spectral index, alpha = d(n_s)/d(ln k) > -0.05.